package diff;

import java.util.*;

/**
 * "A Fast Algorithm for Computing Longest Common Subsequences" by James Hunt and Thomas Szymanski
 * Time: O((R + N)logN), R is amount of pairs of equal elements of input strings (R is in [0; N^2])
 * Memory consumption: O(R + N).

 * @author Arseny Kapoulkine
 */
public class HuntDiffCalculator implements DiffCalculator
{
    private static class Node
    {
        public int i;
        public int j;
        public Node next;
        public Node prev;

        public Node(int i, int j, Node next)
        {
            this.i = i;
            this.j = j;
            this.next = next;
            this.prev = null;
        }
    }

    public Diff calculate(List source, List dest)
    {
        int N = source.size();
        int M = dest.size();

        // Step 1. Build linked lists
        LinkedList[] matchList = new LinkedList[N];

        // Quadratic for now
        for (int i = 0; i < N; ++i)
        {
            matchList[i] = new LinkedList();

            for (int j = 0; j < M; ++j)
                if (source.get(i).equals(dest.get(j)))
                    matchList[i].addFirst(new Integer(j));
        }

        // Step 2. Initialize the thresh array
        int[] thresh = new int[N + 1];

        thresh[0] = 0;

        for (int i = 1; i <= N; ++i)
            thresh[i] = M + 1;

        // Step 3. Compute successive thresh values
        Node[] link = new Node[N+1];

        for (int i = 0; i < N; ++i)
        {
            for (Iterator it = matchList[i].iterator(); it.hasNext(); )
            {
                int j = ((Integer)it.next()).intValue();

                int index = Arrays.binarySearch(thresh, j);

                if (index < 0)
                {
                    // index = -insertion_point - 1
                    int k = -index - 1;

                    thresh[k] = j;
                    link[k] = new Node(i, j, link[k-1]);
                }
            }
        }

        // Step 4. Recover longest common subsequence
        int k = N;

        while (k > 0 && thresh[k] == M+1) --k;

        // Add node which says that source[N] == dest[M] (to handle trailing parts of the text)
        Node ptr = new Node(N, M, link[k]);

        // List is in reverse order, so set up 'prev' pointers
        Node prev = null;

        while (ptr != null)
        {
            ptr.prev = prev;
            prev = ptr;
            ptr = ptr.next;
        }

        Diff result = new Diff();

        // Fill diff with appropriate packets
        int source_line = -1, dest_line = -1;

        for (ptr = prev; ptr != null; ptr = ptr.prev)
        {
            if (source_line + 1 != ptr.i || dest_line + 1 != ptr.j)
            {
                // source[source_line] == dest[dest_line]

                // We have to remove everything in (source_line, ptr.i)
                DiffPacket p = new DiffPacket(source_line + 1, ptr.i);

                // And add everything in (dest_line, ptr.j)
                if (dest_line + 1 != ptr.j)
                    p.contents = new ArrayList();

                for (int i = dest_line + 1; i < ptr.j; ++i)
                    p.contents.add(dest.get(i));

                result.getPackets().add(p);
            }

            source_line = ptr.i;
            dest_line = ptr.j;
        }

        return result;
    }
}
